package com.lb.algorithm;

/**
 * @Author: zhangjun
 * @Date: 2020/6/29 9:33
 * @Description: 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 */
public class Palindromic {
    //方法一：暴力匹配 （Brute Force）
    /*public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;

        int maxLength = 1;
        int begin = 0;

        char[] chars = s.toCharArray();

        //枚举出所有的长度大于1的子串
        for (int i=0;i<len-1;i++) {
            for (int j = i + 1;j<len;j++) {
                if (j - i + 1 > maxLength && validSubStrPalindrome(chars,i,j)) {
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLength);
    }

    *//**
     * 验证子串 s[left..right] 是否为回文串
     *//*
    private boolean validSubStrPalindrome(char[] chars, int left, int right) {
        while (left < right) {
            if (chars[left] != chars[right]) return false;
            left++;
            right--;
        }
        return true;
    }*/

    //方式二
    public String longestPalindrome(String s) {
        //特殊处理
        int len = s.length();
        if (len < 2) return s;

        int maxLength = 1;//默认长度为1
        int begin = 0; //起始左下标从0开始

        //定义二维数组判断回文字符串
        boolean[][] dp = new boolean[len][len];
        //将字符串转成字符数组
        char[] chars = s.toCharArray();

        //单个字符肯定是回文
        for (int i=0;i<len;i++) {
            dp[i][i] = true;
        }

        for (int j=1;j<len;j++) {
            for (int i=0;i<j;i++) {
                if (chars[i] != chars[j]) {
                    dp[i][j]=false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                //记录回文字符的起始和结束下标
                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i +1;
                    begin = i;
                }
            }
        }

        return s.substring(begin,begin + maxLength);
    }

    public static void main(String[] args) {
        String str = "bfsabaqweqeqd";
        Palindromic palindromic = new Palindromic();
        System.out.printf("[%s] 中最长回文数是 [%s]",str,palindromic.longestPalindrome(str));
    }
}
